package pri.zjy.interview;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangjy
 * @description
 * @date 2025/6/12 13:57
 */
public class Test7 {

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        int num = 4;

        List<List<Integer>> ans = findAll(nums, num);
        ans.forEach(System.out::println);
    }

    // 输入int数组（无重复），目标数字num，返回如下：
    // {1, 2, 3} num=4 返回: {1, 1, 1, 1} {1, 3} {1, 1, 2} {2,2}；同一个元素可重复使用
    public static List<List<Integer>> findAll(int[] nums, int num) {
        List<List<Integer>> ans = new ArrayList<>();
        find(nums, num, new ArrayList<>(), ans, 0);

        return ans;
    }

    public static void find(int[] nums, int remain, List<Integer> list, List<List<Integer>> ans, int start) {
        // num减为0，记录当前list
        if (remain == 0) {
            ans.add(new ArrayList<>(list));
            return;
        }

        // 加入后，list元素和 > remain，则直接返回（返回后会移除该元素）
        if (remain < 0) return;

        // 递归
        // 本层递归：先记录当前元素，然后递归调用记录剩余元素，记录后移除最末尾元素，从而找到所有情况
        for (int i = start; i < nums.length; i++) {
            list.add(nums[i]);

            // 递归调用，找下一个remain
            // 下一层从 i 开始，因为同一个元素可重复使用
            find(nums, remain - nums[i], list, ans, i);
            list.remove(list.size() - 1);

            // 不使用nums[i]
//            find(nums, remain, list, ans, i + 1);

            //
//            if (remain - nums[i] == 0) list.remove(list.size() - 1);
        }

//        // 找出所有情况，同一组不考虑顺序
//        Map<Integer, Integer> map = new HashMap<>();
//        for (int i = 0; i < nums.length; i++) {
//            map.put(nums[i], i);
//        }
//        // 每层遍历
//        // 内层找 num-nums[i]，nums[i]也考虑找出所有情况
//        List<List<Integer>> ans = new ArrayList<>();
//        for (int i = 0; i < nums.length; i++) {
//            List<Integer> list = new ArrayList<>();
//            int remain = num - nums[i];
//            for (int j = 0; j < nums.length; j++) {
//                remain = num - nums[j];
//                if (map.containsKey(remain)) {
//                    list.add(remain);
//                }
//            }
//
//            if (remain == 0) ans.add(list);
//
//        }
    }

}
